package com.fr.lintcode;

import org.junit.Test;

/**
*作者：furong
*日期：2017年3月22日
*时间：下午4:19:30
*/
public class Q564 {
    /**
     * @param nums an integer array and all positive numbers, no duplicates
     * @param target an integer
     * @return an integer
     */
    public int backPackVI(int[] nums, int target) {
        if (target <= 0) {
            return 0;
        }
        int length = nums.length;
        int[] dp = new int[target + 1];
        for (int i = 1; i <= target; i++) {
            for (int j = 1; j <= length; j++) {
                if (i < nums[j - 1]) {
                    continue;
                } else if (i == nums[j - 1]) {
                    dp[i]++;
                } else {
                    dp[i] += dp[i - nums[j - 1]];
                }
            }
        }
        return dp[target];
    }

    @Test
    public void testA() {
        int nums[] = { 1, 2, 4 };
        int target = 4;
        System.out.println(backPackVI(nums, target));
    }
}
